#include <stdio.h>
#include <stdlib.h>

//哈夫曼树结点结构
typedef struct {
    //节点权值
    int weight;
    //父结点、左孩子、右孩子在数组中的位置下标
    int parent, left, right;
}HTNode, *HUffmanTree;

//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HUffmanTree tree, int end, int * s1, int * s2) {
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;
    //找到还没构建树的结点
    while (tree[i].parent != 0 && i <= end)
    {
        /* code */
        i++;
    }
    min1 = tree[i].weight;
    *s1 = i;

    i++;
    //找到还没构建树的结点
    while (tree[i].parent != 0 && i <= end)
    {
        /* code */
        i++;
    }

    //对找到的两个结点比较大小，min2为大的，min1为小的
    if(tree[i].weight < min1) {
        min2 = min1;
        *s2 = *s1;
        min1 = tree[i].weight;
        *s1 = i;
    } else {
        min2 = tree[i].weight;
        *s2 = i;
    }
    
    //两个结点和后续的所有未构建成树的结点做比较
    for(int j = i+1; j <= end; j++) {
        //如果有父结点，直接跳过，进行下一个
        if(tree[j].parent != 0) {
            continue;
        }
        //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if(tree[j].weight < min1) {
            min2 = min1;
            min1 = tree[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
        //如果介于两者之间，min2赋值为新的结点的位置下标
        else if(tree[j].weight >= min1 && tree[j].weight < min2) {
            min2 = tree[j].weight;
            *s2 = j;
        }
    }
}

//HT为地址传递的存储哈夫曼树的数组，w为存储结点权重值的数组，n为结点个数
void CreateHuffmanTree(HUffmanTree *tree, int *w, int n) {
    // 如果只有一个编码就相当于0
    if(n <= 1) return;
    // 哈夫曼树总节点数，n就是叶子结点
    int m = 2 * n - 1;
    // 0号位置不用
    *tree = (HUffmanTree)malloc((m+1) * sizeof(HTNode));
    HUffmanTree p = *tree;
    // 初始化哈夫曼树中的所有结点
    for(int i = 1; i <= n; i++) {
        (p+i)->weight = *(w + i - 1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
    //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
    for(int i = n+1; i <= m; i++) {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
    //构建哈夫曼树
    for(int i = n+1; i <= m; i++) {
        int s1, s2;
        Select(*tree, i-1, &s1, &s2);
        (*tree)[s1].parent = (*tree)[s2].parent = i;
        (*tree)[i].left = s1;
        (*tree)[i].right = s2;
        (*tree)[i].weight = (*tree)[s1].weight + (*tree)[s2].weight;
    }
    // for(int i = 1; i <= m; i++) {
    //     int l = (*tree)[i].left;
    //     int r = (*tree)[i].right;
    //     if(l != 0) {
    //         printf("%d ", (*tree)[l].weight);
    //         printf("%d ", (*tree)[i].weight);
    //         printf("%d\n", (*tree)[r].weight);
    //     } 
    // }
}

int main(int argc, char * argv[]) {
    //HUffmanTree tree = (HUffmanTree)malloc(sizeof(HTNode));
    HUffmanTree tree;
    int m[] = {2, 8, 7, 6, 5};
    int n = 5;
    CreateHuffmanTree(&tree, m, n);
    //打印HUffmanTree
    printf("左孩子节点权值\t 父节点权值\t 右孩子节点权值\n");
    for(int i = 1; i <= 2*n -1; i++) {   
        int l = tree[i].left;
        int r = tree[i].right;
        if(l != 0) {     
            printf("%d\t", tree[l].weight);
            printf("%d\t",tree[i].weight);
            printf("%d\t\n", tree[r].weight);
        }
    }
    return 0;
}